package 把二叉搜索树转换为累加树;

import java.util.Stack;

/**
 * @author: AirMan
 * @date: 2025/4/10 13:13
 * @description: 迭代
 */
public class Solution2 {
    public TreeNode convertBST(TreeNode root) {
        // 迭代法
        // 反中序遍历二叉搜索树，遍历过程中不断更新当前的累加值
        TreeNode p = root;
        Stack<TreeNode> stack = new Stack<>();
        int currentSum = 0;
        while (p != null || !stack.isEmpty()){
            if (p!=null){
                // right
                stack.push(p);
                p = p.right;
            }else {
                // mid
                p = stack.pop();
                p.val = currentSum + p.val;
                currentSum = p.val;
                // left
                p = p.left;
            }
        }
        return root;
    }
}
